/* 1) Major changes: separate a CSP instance from the CSP_base
 * class. In CSP_base, we provide the data and methods for
 * AC algorithms and Backtracking algorithms. 
 * For each application (problem instance), we define class
 * CSP which is to set up the atrributes of CSP_base:
 * n,d,e, vars, domains; and implement the virtual methods
 * defined by CSP_base. 
 * After this modification, it should be easier to solve new
 * problems. 
 * cross_link_list is the 'variable based constraint network'.
 * 2) consequences: Thie change will affect the 'revision' 
 * procedure of mac*.cpp which can access a constraint only 
 * through validtuple(i,j,x,y).
 * 1 Apr 2004
 */

#if !defined(__CSP_H)
#define __CSP_H 1

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <list>
#include <stack>
#include <vector>


#define ONEMILLION 1000000

using namespace std;


#ifdef BACK_POINT_SUPPORT
struct BackSupportNode;
#endif
#ifdef FORW_POINT_SUPPORT
struct ForwSupportNode;
#endif

typedef
  struct {
    int yes;
    int pre;
    int next;
#ifdef FORW_POINT_SUPPORT
	ForwSupportNode* supported;
#endif
#ifdef BACK_POINT_SUPPORT
	BackSupportNode* supported;
#endif
  } Domain;

#ifdef BACK_POINT_SUPPORT
#include "bsupport.h"
#endif
#ifdef FORW_POINT_SUPPORT
#include "fsupport.h"
#endif	

// typedef struct {int i,j;} Queue;

typedef struct {
  Domain* dp;
  int domainSize;
  int degree;
} Variable;



class CSP_base {

 protected:
	
    bool debugFlag; 

    //------------variables with permanent value ---------------
    int n, e, d; 
    // Constraint* cn;
    Variable* vars;

    // cross-link-list representation of the variable 
    // based constraint network
#ifdef VAL_COMPUTE
	vector<list<int> > valConnect;
	vector<list<int> > valConflict;
#endif
    list<int> *cross_link_list;
    list<int>::const_iterator cllp;

    //------------variables needs maintained during search------
    // the clock marks the progress of the search procedure
    int curPhase; 

    // the current domain 

    Domain* domain; 
#ifdef BACK_POINT_SUPPORT
	BackSupportList BackSupport;
#endif
#ifdef FORW_POINT_SUPPORT
	ForwSupportList ForwSupport;
#endif
#ifdef USEAC3ADO
	typedef int* Support;
	Support *support;
#endif	
    typedef struct {
      int var;
      int value;
 
      // 'value' is removed due to the instantiation of the
      // variable in phase 'phase', due to isDomRem.
      int phase;
	  int seg;
    } RemovedValue;
    // stack to store the removed values
    // the max size of the stacik is $nd$.
    std::stack<RemovedValue> removedValues;
#ifdef DOMAIN_SPLIT
	std::stack<RemovedValue> splitValues;
	bool domainSplitting;
	int curSeg;
#endif
                                                                                
    void restoreDomains(int);


    //------------disposable variables--------------------------
    // temp variables 
    // Constraint curij, curji; // used in constructing an instance 
    // Constraint currentc; // for validtuple(int x, int y) 


    //------------internal methods------------------------------
    // domain operations
    
    // the dummy value before the first value of a domain
    int headOfDomain();
    // remove a value of a var
    void remove(int, int);
    // insert a value to the domain of a variable
    void insert(int, int);
    // next(var, value) return a the next value of 'value' in
    // the domain of var. 
    int next(int, int); 
    // return the domain of a given variable
    Domain* domainOfVar(int);
    // check the domain a var
    bool empty_domain(int);
    
    //int traverseDomainP;
    
    // whether two variables are in one constraint
    virtual bool related(int, int) = 0; 
    
    // performance analysis of the algorithm
    int num_removed_values;
    int num_cchecks; // number of constraint checks
    int num_cchecks_M; // number of checks in Millions  
    int num_dchecks; // number of domain checks
    int num_dchecks_M; // number of dchecks in Millions
    // for k-residue
    int num_ochecks; // extra cost
    int num_ochecks_M; // extra cost in Millions

#ifdef EXTENDED_STATISTICS
	int *ccheck_levels;
	int *dcheck_levels;
	int *remval_levels;
#endif
    
    // set the curPhase 
    void setPhase(int);

 public:
    CSP_base();

    // initialize the csp instance 
    void initCSP_base();

    // check whether a given tuple satisfies a constraint
    virtual bool validtuple(int, int, int, int) = 0;
    virtual void setCurrentConstraint(int i, int j) = 0;
    virtual bool validtuple(int x, int y) = 0;

    void printDomain(int var);
    virtual void printCSP() = 0; 
  
    // statistics of ac algorithms
    float checks() { return cchecks() + dchecks() + ochecks(); }
    float cchecks() { return (float)num_cchecks_M*ONEMILLION + num_cchecks; }
    float dchecks() { return (float)num_dchecks_M*ONEMILLION + num_dchecks; }
    // for k-residue
    float ochecks() { return (float)num_ochecks_M*ONEMILLION + num_ochecks; }
    // add num to the number of dchecks
    void addDchecks(int num) 
    { 
      num_dchecks += num;
    }
    
    // add num to the number of other checks
    void addOchecks(int num)
    {
      num_ochecks += num;
    }
    // arc consistency algorithm. virtual method for future version
    // will Q be automatically deconstructed?
    virtual ~CSP_base();
};

#endif

